The base register autoincrement addressing mode is implemented in modern processors and architectures, such as in the Intel Itanium™ family of processors and the HP PA-RISC™ architecture, to reduce the address computation overhead The reduction in overhead is achieved by arranging for a memory access instruction to modify its address register operand (through post-increment addressing mode) so that the modified address register value corresponds to the memory address used by a subsequent memory access instruction. By having the subsequent memory access instruction directly sourcing the post-incremented address register, an ALU (arithmetic logic unit) instruction that would otherwise be employed to set up the address for the memory access instruction is eliminated. Besides reducing resource contention, the base register autoincrement addressing mode has also proved to reduce potential instruction cache misses.
To facilitate discussion, FIG. 1A shows an example of six instructions that have been labeled with reference numbers 102, 104, 106, 108, 110, and 112. These reference numbers are not part of the program code; however, they are provided to improve clarity in the discussion. Instructions 102, 106, and 108 set up the address operands for load instructions 104, 108, and 110. In instruction 102, the value of register x is computed from a register t. This value x is then employed in load instruction 104 (representing an example memory access instruction) as the operand for the load instruction. Thus, instruction 104 “1d a=[x]” results in the contents of the memory location specified by register x being loaded into register a. Similarly, instruction 108 “1d b=[y]” results in the contents of the memory location specified by register y being loaded into register b. Likewise, instruction 112 “1d c=[z]” results in the contents of the memory location specified by register z being loaded into register c.
Notice, however, that instructions 102, 106, and 110 all compute their respective operands from a base register t. By converting instructions 102, 104, 106, 108, 110, and 112 to instructions conforming to the base register autoincrement addressing mode, the number of instructions employed to accomplish the operations specified by the sequence of instructions 102, 104, 106, 108, 110, and 112 is reduced, leading to improved execution efficiency.
FIG. 1B illustrates four instructions 114, 116, 118, and 120, representing instructions conforming to the base register autoincrement addressing mode and accomplishing the same operations as those specified in FIG. 1A. Instruction 114 is similar to instruction 102 in that instruction 114 sets up the operand x for the next memory access instruction that employs this operand value. Instruction 116 “1d a=[x], 4” is essentially similar to analogous instruction 104 with one important difference. In instruction 116, the “, 4” portion indicates that the value of x is incremented by 4 after the contents of the address location specified by operand x has been loaded into register a. This post-incrementing operation, which occurs in the same cycle as the load operation, eliminates the need to set up operand x again for the next load operation (e.g., load operation 118).
Note that instruction 116 accomplishes the same result as instructions 104 and 106 of FIG. 1A. This is because the operands of instructions 108 and 104 (i.e., y and x) are both derived from base register t and differ by 4 with respect to one another. By post-incrementing the operand x by 4 after load instruction 116, the operand x is set up for the next load instruction 118.
Similarly, note that instruction 118 accomplishes the same result as instructions 108 and 110 of FIG. 1A. This is because the operands of instructions 112 and 108 (i.e., z and y) are both derived from base register t and differ by 16 with respect to one another. By post-incrementing the operand x by 16 after load instruction 118, the operand x is set up for the next load instruction 120.
Load instruction 120 also conforms to the base register autoincrement addressing mode. However, since there are no subsequent memory access instructions that employ base register t in the calculation of the address operand, there is no need to autoincrement the value x after loading into register c. To put it another way, instruction 120 autoincrements the value x by zero.
Thus, the six instructions of FIG. 1A have been optimized and result in four instructions in FIG. 1B when the base register autoincrement addressing mode is employed. Note that the optimization is possible because the memory access instructions of FIG. 1A employ operands that are computed from the same base register t.
The above-discussed optimization may be performed by a human programmer when working with processors and architectures that support the base register autoincrement addressing mode. Such manual optimization is, however, tedious, time-consuming, error-prone, and susceptible to missed optimization opportunities whereby the programmer simply overlooks possible candidate instructions for optimization. In the software engineering process, automated code optimization (i.e., optimization performed by the computer) is therefore desirable. Such automated code optimization employs computer-implemented techniques capable of identifying candidate codes for optimization, as well as computer-implemented techniques for performing the optimization.
The inventors are aware that U.S. Pat. No. 6,151,705 issued to Santhanam on Nov. 21, 2000 (hereinafter “the '705 patent”) discloses techniques for optimizing addressing instructions that occur in loops, e.g., for (i=1; i<8; i++), which memory address instructions specify an address that is a linear function of a loop induction variable (e.g., i). Further details may be obtained by reference to the '705 patent, which is publicly available.
To the inventors' best knowledge, however, there are no prior art techniques for automatically optimizing straight-line, non-inductive code such as those discussed in the example of FIG. 1A. This patent application is directed toward techniques for automating the optimization of straight-line, non-inductive code to take advantage of the efficiency offered by the base register autoincrement addressing mode.